package misc;

import java.util.ArrayList;
import model.Aluno;
import model.Popularidade;

public class Sorting {
    private ArrayList<Integer> lista_rm = new ArrayList<Integer>();
    
    private ArrayList<Aluno> alunos_rm = new ArrayList<Aluno>();
    private ArrayList<Aluno> alunos_nome = new ArrayList<Aluno>();
    
    private ArrayList<Popularidade> popularidade = new ArrayList<Popularidade>();
    
    private ArrayList<String> aluno_distancia = new ArrayList<String>();

    public ArrayList<Integer> getLista_rm() {
        return lista_rm;
    }

    public void setLista_rm(ArrayList<Integer> lista_rm) {
        this.lista_rm = lista_rm;
    }

    public ArrayList<Aluno> getAlunos_rm() {
        return alunos_rm;
    }

    public void setAlunos_rm(ArrayList<Aluno> alunos_rm) {
        this.alunos_rm = alunos_rm;
    }

    public ArrayList<Aluno> getAlunos_nome() {
        return alunos_nome;
    }

    public void setAlunos_nome(ArrayList<Aluno> alunos_nome) {
        this.alunos_nome = alunos_nome;
    }

    public ArrayList<Popularidade> getPopularidade() {
        return popularidade;
    }

    public void setPopularidade(ArrayList<Popularidade> popularidade) {
        this.popularidade = popularidade;
    }

    public ArrayList<String> getAluno_distancia() {
        return aluno_distancia;
    }

    public void setAluno_distancia(ArrayList<String> aluno_distancia) {
        this.aluno_distancia = aluno_distancia;
    }
    
    
    // Ordenação por QuickSort Híbrido:
    public void quicksort_lista_rm(int esquerda, int direita) {
        if(direita - esquerda < 4) {
            insertion_sort_lista_rm(esquerda, direita);
        }
        else {
            int index = particiona_lista_rm(esquerda, direita);
            if(esquerda < index - 1) {
                quicksort_lista_rm(esquerda, index-1);
            }
            if(index < direita) {
                quicksort_lista_rm(index, direita);
            }
        }
    }
    // Sub-Função de QuickSort
    private Integer particiona_lista_rm(int esquerda, int direita) {
        int i = esquerda;
        int j = direita;
        Integer aux;
        
        System.out.println("\n# QuickSort - Tamanho do Sub-Vetor: " + String.valueOf((direita - esquerda)+1) + " #");
        
        int pivo = lista_rm.get((esquerda + direita) / 2);
        
        while(i <= j) {
            while(lista_rm.get(i) < pivo) {
                i++;
            }
            while(lista_rm.get(j) > pivo) {
                j--;
            }
            if(i <= j) {
                aux = lista_rm.get(i);
                lista_rm.set(i, lista_rm.get(j));
                lista_rm.set(j, aux);
                i++;
                j--;
            }
        }
    
    return(i);
    }
    // Se o Sub-Vetor for muito pequeno, melhor ordenar por Insertion Sort:
    private void insertion_sort_lista_rm(int esquerda, int direita) {
        int k, l;
        Integer aux;
        
        for(k = esquerda + 1 ; k <= direita ; k++) {
            aux = lista_rm.get(k);
            for(l = k - 1 ; l >= esquerda && aux < lista_rm.get(l) ; l--) {
                lista_rm.set(l+1, lista_rm.get(l));
            }
            lista_rm.set(l+1, aux);
            insertion_sort_passo(esquerda, direita, k);
        }
        System.out.println();
    }
    private void insertion_sort_passo(int esquerda, int direita, int cont) {
        System.out.print("\n# Insertion Sort: ");
        for(int k = esquerda ; k <= direita ; k++) {
            if(k == cont) {
                System.out.print("|" + String.valueOf(lista_rm.get(k)) + "| ");
            }
            else {
                System.out.print(String.valueOf(lista_rm.get(k)) + " ");
            }
        }
        System.out.print(" #");
    }
    
    // Ordenação por Insertion Sort:
    public void insertion_sort_alunos_rm() {
        int k, l;
        Aluno aux;
        for(k = 1 ; k < alunos_rm.size() ; k++) {
            aux = alunos_rm.get(k);
            for(l = k - 1 ; l >= 0 && aux.getRm() < alunos_rm.get(l).getRm() ; l--) {
                alunos_rm.set(l+1, alunos_rm.get(l));
            }
            alunos_rm.set(l+1, aux);
        }
    }
    
    // Ordenação por Selection Sort:
    public void selection_sort_alunos_nome() {
        int k, l, menor;
        Aluno aux;
        for(k = 0 ; k < alunos_nome.size() - 1 ; k++) {
            menor = k;
            for(l = k+1 ; l < alunos_nome.size() ; l++) {
                if(alunos_nome.get(l).getNome().compareTo(alunos_nome.get(menor).getNome()) < 0) {
                    menor = l;
                }
            }
            if(menor != k) {
                aux = alunos_nome.get(k);
                alunos_nome.set(k, alunos_nome.get(menor));
                alunos_nome.set(menor, aux);
            }
        }
    }
    
    public void quicksort_popularidade(int esquerda, int direita) {
        int index = particiona_popularidade(esquerda, direita);
        if(esquerda < index - 1) {
            quicksort_popularidade(esquerda, index-1);
        }
        if(index < direita) {
            quicksort_popularidade(index, direita);
        }
    }
    
    private Integer particiona_popularidade(int esquerda, int direita) {
        int i = esquerda;
        int j = direita;
        Popularidade aux;
        
        int pivo = popularidade.get((esquerda + direita) / 2).getApontamentos();
        while(i <= j) {
            while(popularidade.get(i).getApontamentos() > pivo) {
                i++;
            }
            while(popularidade.get(j).getApontamentos() < pivo) {
                j--;
            }
            if(i <= j) {
                aux = popularidade.get(i);
                popularidade.set(i, popularidade.get(j));
                popularidade.set(j, aux);
                i++;
                j--;
            }
        }
    
    return(i);
    }
    
    public void insertion_sort_aluno_distancia() {
        int k, l;
        String aux;
        
        for(k = 1 ; k < aluno_distancia.size() ; k++) {
            aux = aluno_distancia.get(k);
            for(l = k - 1 ; l >= 0 && aux.compareTo(aluno_distancia.get(l)) < 0 ; l--) {
                aluno_distancia.set(l+1, aluno_distancia.get(l));
            }
            aluno_distancia.set(l+1, aux);
        }
    }
    
    public Integer busca_binaria_alunos_rm(Integer rm, int esquerda, int direita) {
        while(esquerda <= direita) {
            int meio = (esquerda + direita) / 2;
            System.out.println("# Busca Binária:\nEsquerda: " + String.valueOf(alunos_rm.get(esquerda).getRm()));
            System.out.println("Direita: " + String.valueOf(alunos_rm.get(direita).getRm()) + "\nMeio: " + String.valueOf(alunos_rm.get(meio).getRm()));
            System.out.println("Pesquisa: " + String.valueOf(rm) + "\n");
            if(alunos_rm.get(meio).getRm() - rm == 0) {
                System.out.println("\nMeio = RM\n");
                return(meio);
            }
            else {
                if(rm - alunos_rm.get(meio).getRm() < 0) {
                    return(busca_binaria_alunos_rm(rm, esquerda, meio-1));
                }
                else if(rm - alunos_rm.get(meio).getRm() > 0) {
                    return(busca_binaria_alunos_rm(rm, meio+1, direita));
                }
            }
        }
        
    return(-1);
    }
}
